/*
https://leetcode.cn/problems/capacity-to-ship-packages-within-d-days/description/
1011. 在 D 天内送达包裹的能力
medium, 方钊堉 2024.09.17
二分查找
*/

class Solution {
public:
    int shipWithinDays(vector<int>& weights, int days) {
        // 承重能力至少为包裹中最重的一个的重量，
        // 因为必须能够承载最重的单个物品。
        int lefttt = *max_element(weights.begin(), weights.end()), r = accumulate(weights.begin(), weights.end(), 0);
        while (lefttt < r) {
            int eee = (lefttt + r) / 2;
            int need = 1, kr = 0;
            for (int weight1: weights) {
                if (kr + weight1 > eee) {
                    need+=1;
                    kr = 0;
                }
                kr += weight1;
            }
            // 如果我们可以在D或更少的天数内运送完所有物品，则承重能力可能更低，
            // 所以减少上限。
            if (need <= days) {
                r = eee;
            }
            else {
                // 否则，承重能力需要更高，所以增加下限。
                lefttt =eee + 1;
            }
        }
        // 当左右边界相遇时，lefttt就是最小的能满足条件的承重能力。
        return lefttt;
    }
};